package com.berchen.offer;

/**
 * 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回 true ,否则返回 false 。假设输入的数组的任意两个数字都互不相同。
 *
 * 数据范围： 节点数量 0 \le n \le 10000≤n≤1000 ，节点上的值满足 1 \le val \le 10^{5}1≤val≤10
 * 5
 *   ，保证节点上的值各不相同
 * 要求：空间复杂度 O(n)O(n) ，时间时间复杂度 O(n^2)O(n
 * 2
 *  )
 * 提示：
 * 1.二叉搜索树是指父亲节点大于左孩子节点，但是小于右孩子节点。
 * 2.该题我们约定空树不是二叉搜索树
 * 3.后序遍历是指按照 “左子树-右子树-根节点” 的顺序遍历
 *
 * 二叉搜索树的后续遍历的 数组中 最后一个数就是树的根节点
 * 从根节点前面节点找到第一个大于根节点的数 这个就是根节点左子树和右子树的分界点
 * 的保证根节点的左子树都小于根节点  根节点的左子树都大于根节点
 *
 */
public class Test04 {
    public static void main(String[] args) {
        int []arr={1,2,3,4,5,6,7,-5,-1};
        Test04 test04 = new Test04();
        System.out.println(test04.VerifySquenceOfBST(arr));
    }

    public boolean VerifySquenceOfBST(int [] sequence) {

        if(sequence.length==0){
            return false;
        }
        return diGui(sequence,0,sequence.length-1);
    }

    /**
     * 递归
     * @param arr
     * @param start
     * @param end
     * @return
     */
    public boolean diGui(int[] arr,int start ,int end ){

        if(start>end){
            return false;
        }
        if(start==end){
            return true;
        }
        // 获取根节点 后续遍历 根节点就是end位置的
        int root=arr[end];
        int index=-1;
        // 遍历 找到第一个大于根节点的值 这个位置就是根节点的左子树和右子树的分界点
        for(int i =start;i<end;i++){
            if(arr[i]>root){
                index=i;
                break;
            }
        }
        if(index==-1){// 只有左子树
            return diGui(arr,start,end-1);
        }
        else {
            if(index==start){// 只有右子树

                // 根节点的右子树都大于根节点
                for(int i=start;i<end;i++){
                    if(arr[i]<root){
                        return false;
                    }
                }
                return diGui(arr,start,end-1);
            }else { // 左右子树都有
                // 根节点的左子树都小于根节点
                for(int i =start;i<index;i++){
                    if(arr[i]>root){
                        return false;
                    }
                }
                // 根节点的右子树 都大于根节点
                for(int i =index;i<end;i++){
                    if(arr[i]<root){
                        return false;
                    }
                }
                boolean flag=diGui(arr,start,index-1);
                if(flag){
                    return diGui(arr,index,end-1);
                }
            }
        }
        return false;
    }
}
